Set Relations

Set Relations (Basic Comparison)

Before defining mathematical relations between elements of sets, it's useful to review the basic ways sets themselves can relate to each other based on their elements. These are essentially comparisons of the entire collections of elements.

Basic Comparisons Between Sets:

• Subset ($\subseteq$):

  Set $A$ is a subset of set $B$ if every element of $A$ is also an element of $B$. This is the fundamental relation of containment.

  $A \subseteq B \iff (\forall x, x \in A \implies x \in B)$

  Example:

  If $A = \{ \text{Red, Blue} \}$ and $B = \{ \text{Red, Blue, Green, White} \}$, then $A \subseteq B$ because both Red and Blue are in B.

• Superset ($\supseteq$):

  Set $B$ is a superset of set $A$ if $A$ is a subset of $B$. It's the same relationship as subset, just viewed from the perspective of the larger set.

  $B \supseteq A \iff A \subseteq B$

  Example:

  If $A = \{1, 2\}$ and $B = \{0, 1, 2, 3\}$, then $B \supseteq A$ because $A \subseteq B$.

• Proper Subset ($\subset$ or $\subsetneq$):

  Set $A$ is a proper subset of set $B$ if $A$ is a subset of $B$ ($A \subseteq B$) and $A$ is not equal to $B$ ($A \neq B$). This means $B$ must contain all elements of $A$ plus at least one additional element.

  $A \subset B \iff (A \subseteq B \text{ and } A \neq B)$

  Example:

  If $A = \{ \text{Dog} \}$ and $B = \{ \text{Dog, Cat} \}$, then $A \subset B$. Every element of A (Dog) is in B, but B also contains Cat, which is not in A.

• Proper Superset ($\supset$ or $\supsetneq$):

  Set $B$ is a proper superset of set $A$ if $B$ is a superset of $A$ ($B \supseteq A$) and $B$ is not equal to $A$ ($B \neq A$). This is the reverse perspective of the proper subset relationship.

  $B \supset A \iff (B \supseteq A \text{ and } B \neq A)$

  Example:

  If $P = \{1, 2, 3, 4\}$ and $Q = \{1, 2\}$, then $P \supset Q$ because $P \supseteq Q$ and $P \neq Q$.

• Equal Sets (=):

  Set $A$ is equal to set $B$ if they contain precisely the same elements. This is the case if and only if $A$ is a subset of $B$ and $B$ is a subset of $A$.

  $A = B \iff (A \subseteq B \text{ and } B \subseteq A)$

  Example:

  If $A = \{ \text{L, I, S, T, E, N} \}$ and $B = \{ \text{S, I, L, E, N, T} \}$, then $A = B$ because they have the same distinct letters.

• Not a Subset ($\not\subseteq$):

  Set $A$ is not a subset of set $B$ if there exists at least one element in $A$ that is not present in $B$.

  $A \not\subseteq B \iff (\exists x \text{ such that } x \in A \text{ and } x \notin B)$

  Example:

  If $A = \{1, 2, 4\}$ and $B = \{1, 2, 3\}$, then $A \not\subseteq B$ because $4 \in A$ but $4 \notin B$. Similarly, $B \not\subseteq A$ because $3 \in B$ but $3 \notin A$.

• Disjoint Sets:

  Two sets $A$ and $B$ are called disjoint if they have no elements in common. Their intersection is the empty set.

  A and B are disjoint $\iff A \cap B = \emptyset$

  Example:

  If $E = \{ \text{even numbers} \}$ and $O = \{ \text{odd numbers} \}$, and $U = \mathbb{Z}$, then $E$ and $O$ are disjoint because no integer is both even and odd.

• Overlapping Sets (or Intersecting Sets):

  Two sets $A$ and $B$ are overlapping or intersecting if they have at least one element in common. Their intersection is a non-empty set.

  A and B are overlapping $\iff A \cap B \neq \emptyset$

  Example:

  If $P = \{ \text{Prime numbers} \}$ and $E = \{ \text{Even numbers} \}$, then $P$ and $E$ are overlapping because they share the element 2 ($P \cap E = \{2\} \neq \emptyset$).

These basic relationships provide a foundation for understanding how sets can be related before we delve into the formal definition of a "relation" between elements.

Relations on a Set: Definition

In mathematics, the term "relation" is more specific than just comparing sets. A mathematical relation defines a specific association or connection between elements from one set to elements of another set (which can be the same set).

The formal definition of a relation is built upon the concept of the Cartesian product of sets.

Relation from Set A to Set B

Let $A$ and $B$ be two non-empty sets. A relation $R$ from set $A$ to set $B$ is defined as any subset of the Cartesian product $A \times B$.

Formal Definition:

This means that a relation $R$ is a collection of ordered pairs $(a, b)$, where the first component $a$ is an element taken from set $A$, and the second component $b$ is an element taken from set $B$. The specific ordered pairs included in $R$ are determined by the rule or condition that defines the relation.

Membership in a Relation:

• If an ordered pair $(a, b)$ belongs to the relation $R$ (i.e., $(a, b) \in R$), we say that "$a$ is related to $b$ by the relation $R$". This is often written using an infix notation as $a R b$.
• If an ordered pair $(a, b)$ does not belong to the relation $R$ (i.e., $(a, b) \notin R$), we say that "$a$ is not related to $b$ by the relation $R$". This can be written as $a \not R b$.

Essentially, a relation acts like a filter on the Cartesian product $A \times B$, selecting only those pairs that satisfy the given rule of the relation.

Answer:

Relation on a Set A

A special case is when the relation is defined between elements of the same set. A relation $R$ on a set $A$ (or a relation from $A$ to $A$) is defined as any subset of the Cartesian product $A \times A$.

Formal Definition:

In this case, the ordered pairs are of the form $(a_1, a_2)$, where both the first and second components, $a_1$ and $a_2$, are elements of the same set $A$.

Answer:

Total Number of Relations

The number of possible relations that can be defined between two sets (or on a single set) depends on the number of elements in the sets.

Let set $A$ be a finite set with $|A| = p$ elements.

Let set $B$ be a finite set with $|B| = q$ elements.

The Cartesian product $A \times B$ is the set of all ordered pairs $(a, b)$ where $a \in A$ and $b \in B$. The number of elements in $A \times B$ is $|A \times B| = |A| \times |B| = pq$.

A relation $R$ from $A$ to $B$ is any subset of $A \times B$.

The total number of possible subsets of a set with $n$ elements is $2^n$ (this is the cardinality of the power set).

Since $A \times B$ is a set containing $pq$ ordered pairs (elements), the total number of possible subsets of $A \times B$ is $2^{pq}$.

Therefore, the total number of possible relations from a set $A$ with $p$ elements to a set $B$ with $q$ elements is $2^{pq}$.

If the relation is on a single set $A$ with $|A|=p$, the relation is a subset of $A \times A$. The number of elements in $A \times A$ is $|A| \times |A| = p \times p = p^2$. The total number of possible relations on set $A$ is the number of subsets of $A \times A$, which is $2^{p^2}$.

Representation of a Relation (Set Form, Arrow Diagram)

A relation, being a set of ordered pairs, can be represented in several ways. The choice of representation often depends on the nature of the sets involved (finite or infinite) and the complexity of the relation's rule.

Methods of Representing a Relation

1. Set Form (Roster Form)

   This is the most fundamental way to represent a relation $R$. It involves listing all the ordered pairs $(a, b)$ that belong to the relation, enclosed within curly braces. This method is practical for relations involving finite sets with a relatively small number of ordered pairs.

   Example:

   Let $A = \{ \text{Red, Blue, Green} \}$ and $B = \{ \text{Apple, Grape} \}$. A relation $R$ from $A$ to $B$ defined by "is the colour of" could be:

   $R = \{ (\text{Red, Apple}), (\text{Green, Apple}), (\text{Green, Grape}) \}$

   This tells us that Red is related to Apple, Green is related to Apple, and Green is related to Grape by this relation.

2. Set-Builder Form

   This method describes the relation by stating the rule or property that the ordered pairs must satisfy. It is particularly useful for relations involving large or infinite sets where listing all pairs is impossible.

   Example:

   Let $\mathbb{Z}$ be the set of integers. A relation $R$ on $\mathbb{Z}$ can be defined as "is less than or equal to".

   $R = \{ (a, b) \mid a \in \mathbb{Z}, b \in \mathbb{Z}, \text{ and } a \le b \}$

   This relation includes pairs like $(1, 5)$, $(-3, -1)$, $(0, 0)$, etc., but does not include pairs like $(5, 1)$ or $(0, -2)$. Listing all these pairs is impossible as $\mathbb{Z}$ is infinite.

3. Arrow Diagram (Mapping Diagram)

   This is a visual representation, especially helpful for relations between finite sets. It provides a clear picture of which elements from the first set are related to which elements in the second set.

   Construction:

   • Draw two shapes (usually ovals or rectangles) representing the sets $A$ (the domain set) and $B$ (the codomain set).
   • Write the elements of set $A$ inside the first shape and the elements of set $B$ inside the second shape.
   • For every ordered pair $(a, b)$ that belongs to the relation $R$ (i.e., if $a R b$), draw an arrow starting from the element $a$ in set $A$ and pointing to the element $b$ in set $B$.

   ---

   Example 1. Let $A = \{p, q, r\}$ and $B = \{1, 2, 3, 4\}$. Let $R$ be the relation from $A$ to $B$ defined by $R = \{(p, 2), (q, 1), (r, 2), (r, 4)\}$. Represent $R$ using an arrow diagram.

   Answer:

   Given: $A = \{p, q, r\}$, $B = \{1, 2, 3, 4\}$, $R = \{(p, 2), (q, 1), (r, 2), (r, 4)\}$.

   Representation:

   Draw two ovals, label the first 'Set A' and the second 'Set B'.

   Place elements p, q, r in Set A oval and elements 1, 2, 3, 4 in Set B oval.

   Draw arrows based on the ordered pairs in R:

   • Draw an arrow from $p$ to $2$ (because $(p, 2) \in R$).
   • Draw an arrow from $q$ to $1$ (because $(q, 1) \in R$).
   • Draw an arrow from $r$ to $2$ (because $(r, 2) \in R$).
   • Draw an arrow from $r$ to $4$ (because $(r, 4) \in R$).

   

   ---

   Example 2. Let $A = \{1, 2, 3\}$. Consider the relation $R$ on $A$ defined by $R = \{(a, b) \mid a, b \in A, a \le b\}$. Represent $R$ using an arrow diagram.

   Answer:

   Given: $A = \{1, 2, 3\}$, Relation $R = \{(a, b) \mid a, b \in A, a \le b\}$ on $A$.

   To Find: Arrow diagram for R.

   Solution:

   First, write the relation $R$ in roster form by finding all pairs $(a, b)$ from $A \times A$ where $a \le b$:

   • $a=1$: $(1, 1), (1, 2), (1, 3)$ (since $1 \le 1, 1 \le 2, 1 \le 3$)
   • $a=2$: $(2, 2), (2, 3)$ (since $2 \le 2, 2 \le 3$; $2 \not\le 1$)
   • $a=3$: $(3, 3)$ (since $3 \le 3$; $3 \not\le 1, 3 \not\le 2$)

   $R = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$

   Since the relation is on set A, we draw one oval representing set A and place its elements inside.

   Draw arrows based on the pairs in R:

   • From 1 to 1
   • From 1 to 2
   • From 1 to 3
   • From 2 to 2
   • From 2 to 3
   • From 3 to 3

   

4. Table Form

   For relations between finite sets, a table or matrix can be used. The rows represent elements of the first set (Domain set), and the columns represent elements of the second set (Codomain set). A mark (like a checkmark or 1) is placed at the intersection of a row and column if the corresponding ordered pair is in the relation.

   Example:

   Using the relation from Example 1, $A = \{p, q, r\}$, $B = \{1, 2, 3, 4\}$, $R = \{(p, 2), (q, 1), (r, 2), (r, 4)\}$.

   $A \setminus B$	1	2	3	4
   p		✓
   q	✓
   r		✓		✓

   The checkmark at (p, 2) indicates that the pair (p, 2) is in the relation R.

   Example:

   Using the relation from Example 2, $A = \{1, 2, 3\}$, $R = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$ on set A.

   $A \setminus A$	1	2	3
   1	✓	✓	✓
   2		✓	✓
   3			✓

5. Graphical Form

   When the sets involved are subsets of the real numbers (like $\mathbb{Z}, \mathbb{Q}, \mathbb{R}$), a relation $R$ (which is a subset of the Cartesian product, e.g., $\mathbb{R} \times \mathbb{R}$) can be visualized by plotting the ordered pairs $(x, y) \in R$ as points on a Cartesian coordinate plane.

   Example:

   The relation $R = \{(x, y) \in \mathbb{R} \times \mathbb{R} \mid y = x^2 \}$. The pairs in this relation are of the form $(x, x^2)$, such as $(0, 0), (1, 1), (-1, 1), (2, 4), (-2, 4)$, etc. Plotting these points on the xy-plane gives the familiar graph of a parabola.
   
   (Imagine an image showing the graph of the parabola $y=x^2$ on a coordinate plane).

   Example:

   The relation $R = \{(x, y) \in \mathbb{Z} \times \mathbb{Z} \mid y = 2x + 1 \}$. The pairs are $(x, 2x+1)$ where $x$ is an integer, e.g., $(-1, -1), (0, 1), (1, 3), (2, 5)$, etc. Plotting these on the xy-plane would result in a series of discrete points lying on the line $y=2x+1$.
   
   (Imagine an image showing discrete points $(..., (-1,-1), (0,1), (1,3), (2,5), ...)$ plotted on a coordinate plane).

Choosing the appropriate representation can greatly aid in understanding the properties and characteristics of a relation.

Domain and Range of a Relation

For any relation $R$ defined from a set $A$ to a set $B$ ($R \subseteq A \times B$), we can identify specific subsets of $A$ and $B$ that are directly involved in the relation. These subsets are called the domain and the range of the relation. The set $B$ itself is called the codomain.

Domain of a Relation

The domain of a relation $R$ from set $A$ to set $B$ is the set of all first components of the ordered pairs that belong to the relation $R$. It is the set of elements in $A$ from which arrows originate in the arrow diagram.

Notation:

The domain of relation $R$ is denoted by Domain$(R)$ or Dom$(R)$.

Formal Definition:

The domain of $R$ is always a subset of the starting set $A$, i.e., Domain$(R) \subseteq A$.

Range of a Relation

The range of a relation $R$ from set $A$ to set $B$ is the set of all second components of the ordered pairs that belong to the relation $R$. It is the set of elements in $B$ to which arrows point in the arrow diagram.

Notation:

The range of relation $R$ is denoted by Range$(R)$ or Ran$(R)$.

Formal Definition:

The range of $R$ is always a subset of the target set $B$, i.e., Range$(R) \subseteq B$.

Codomain of a Relation

The codomain of a relation $R$ from set $A$ to set $B$ is simply the entire target set $B$.

It represents the set of all potential second components of the ordered pairs in the relation.

By definition of Range, the range of a relation is always a subset of its codomain.

Answer:

Answer: